#include"sort.h"

void swap(int* a,int* b)
{
    int tem=*a;
    *a=*b;
    *b=tem;
}
void InsertSort(int* a, int n)
{
    for(int i=1;i<n;i++)
    {
    //[0,i-1]有序，i与[0,i-1]比较，控制[0,i]有序
        int j=0;
        int tem=a[i];
        for(j=i-1;j>=0;j--)
        {
            if(tem<a[j])
            {
                a[j+1]=a[j];
            }
            else
            {
                break;
            }
        }
        a[j+1]=tem;
    }
}

void ShellSort(int* a, int n)
{
    int gap=n;
    while(gap>1)
    {
        
        gap=gap/3+1;
        //gap组数据排序
        for(int i=0;i<n-gap;i++)
        {
            //[0,i]间隔为gap的数据有序，将i+gap与[0,i]排序，保证[0,i+gap]有序,多组并排
            int j=0;
           int tem=a[i+gap];
           for(j=i;j>=0;j-=gap)
           {
                if(tem<a[j])
                    a[j+gap]=a[j];
                else
                    break;
           }
           a[j+gap]=tem;
        }

    }
}

void BubbleSort(int* a, int n)
{
    for(int i=0;i<n-1;i++)
    {
        int flag=0;
        for(int j=0;j<n-i-1;j++)
        {
            if(a[j]>a[j+1])
            {
                swap(&a[j],&a[j+1]);
                flag=1;
            }
        }
        if(flag==0)
            break;
    }
}

void mind(int* a,int left,int right)
{
    int tem=left+(right-left)/2;
    if(a[left]>a[tem])
    {
        if(a[tem]>a[right])
        swap(&a[tem],&a[left]);
        else if(a[left]>a[right])
        swap(&a[left],&a[right]);

    }
    else
    {
        if(a[tem]<a[right])
        swap(&a[tem],&a[left]);
        else if(a[left]<a[right])
        swap(&a[left],&a[right]);
    }
}
int PartSort1(int* a, int left, int right)
{
    if(left>=right)
    return 0;
    //三数取中
    mind(a,left,right);
    int tem=a[left];
    int cur=left+1;
    int l=left;
    int r=right;
    while(cur<=r)
    {
        if(a[cur]<tem)
        {
            swap(&a[cur],&a[l]);
            l++;cur++;›
        }
        else if(a[cur]>tem)
        {
            swap(&a[cur],&a[r]);
            r--;
        }
        else
        {
            cur++;
        }

    }
    //[left,l-1],[l,r],[r+1,right]
    PartSort1(a,left,l-1);
    PartSort1(a,r+1,right);
}

int PartSort2(int* a, int left, int right)
{

}

void CountSort(int* a, int n)
{
    //找出数组最大最小值，求出计数范围
    int min=a[0],max=a[0];
    for(int i=1;i<n;i++)
    {
        if(a[i]<min)
            min=a[i];
        if(a[i]>max)
            max=a[i];
    }
    //统计数据
    int* ret=(int *)calloc(max-min+1,sizeof(int));
    //int ret[max-min]=0;
    for(int i=0;i<n;i++)
    {
        ret[a[i]-min]++;
    }
    //替换原始数据
    for(int i=0;i<n;i++)
    {
        int j=0;
        while(ret[j]==0)
            j++;
        a[i]=j+min;
        ret[j]--;
    }

}
void _mergesort(int* a,int *tem,int beign,int end)
{
    //当递归到只有一个元素时结束
    if(beign>=end)
        return ;
    int mid=beign+(end-beign)/2;
    _mergesort(a,tem,beign,mid);
    _mergesort(a,tem,mid+1,end);

    //归并到TEM中，后再拷贝回原数组
    int r=mid+1;
    int l=beign;
    int i=beign;
    while(l<=mid&&r<=end)
    {
        if(a[l]>=a[r])
        {
            tem[i]=a[r];
            r++;
        }
        else
        {
            tem[i]=a[l];
            l++;
        }
        i++;
    }
    
    while(l<=mid)
    {
        tem[i++]=a[l++];
        
    }
    while(r<=end)
    {
        tem[i++]=a[r++];
    }
    //memcupy()
    memcpy(a+beign,tem+beign,sizeof(int)*(end-beign+1));

}
void MergeSort(int* a, int n)
{
    int* tem=(int* )malloc(n*sizeof(int));
    _mergesort(a,tem,0,n-1);
    //memcpy(a,tem,sizeof(int)*n);
}